//
//  FindSubsequences.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/8/25.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  491. 递增子序列

import UIKit

/*
 491. 递增子序列
 给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

 示例:

 输入: [4, 6, 7, 7]
 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
 说明:

 给定数组的长度不会超过15。
 数组中的整数范围是 [-100,100]。
 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。
 */

class FindSubsequences: NSObject {
    
    var resultArr:[[Int]] = []
    var hashMap:[[Int]:String] = [:]
    
    func findSubsequences(_ nums: [Int]) -> [[Int]] {
        
        self.dfs(0, [], nums)
        
        return resultArr
    }
    

    func dfs(_ startIndex: Int, _ tmpArr: [Int], _ sourceArr: [Int]){
        
        var tmpArr = tmpArr
        
        if tmpArr.count > 1{
            if tmpArr.last! >= tmpArr[tmpArr.count-2]{
                if hashMap[tmpArr] == nil{
                    resultArr.append(tmpArr)
                    hashMap[tmpArr] = "X"
                }
            }else{
                return
            }
        }
        
        for i in startIndex ..< sourceArr.count{
            tmpArr.append(sourceArr[i])
            self.dfs(i + 1, tmpArr, sourceArr)
            tmpArr.removeLast()
        }
    }
}
